package zw_101_200.zw_191_位1的个数;

public class Solution {

    public static void main(String[] args) {
        int n = 11110;
        System.out.println(hammingWeight(n));
    }

    /**
     * 位运算优化
     * 观察这个运算：n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
     * 如：6 & (6−1)=4,6=(110)2,4=(100)2，运算结果 44 即为把 66 的二进制位中的最低位的 11 变为 00 之后的结果。
     * 这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 n 与 n−1 做与运算，直到 n 变为 0 即可。
     * 因为每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数。
     * @param n
     * @return
     */
//    public static int hammingWeight(int n) {
//        int ret = 0;
//        while (n != 0) {
//            n &= n - 1;
//            ret++;
//        }
//        return ret;
//    }


    /**
     * 右移 32 次
     * 使用 n & 1 得到二进制末尾是否为 1；
     * 把 n 右移 1 位，直至结束。
     *
     * Java 中的 算术右移 和 逻辑右移 。
     * 算术右移 >> ：舍弃最低位，高位用符号位填补；
     * 逻辑右移 >>> ：舍弃最低位，高位用 0 填补。
     * 那么对于负数而言，其二进制最高位是 1，如果使用算术右移，那么高位填补的仍然是 1。也就是 n 永远不会为 0。
     * 在 Java 中需要使用逻辑右移，即 >>> ，while 的判断条件才能是 n != 0 。
     * @param n
     * @return
     */
    public static int hammingWeight(int n) {
        int count = 0;
        while (n != 0){
            count += n & 1;
            n >>>= 1;
        }
        return count;
    }
}